using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace BigNumbers
{
    /// <summary>
    /// Equation management class
    /// </summary>
    public class Calculus
    {
        #region Public Enum
        /// <summary>
        /// List of methods to solve equations f(x) = b
        /// </summary>
        public enum SolveType
        {
            Dichotomy
        }
        #endregion

        #region Delegates
        /// <summary>
        /// Function to use in the Solve Method
        /// </summary>
        public delegate BigInt UnaryFunction(BigInt x);
        #endregion

        #region Static public Methods
        /// <summary>
        /// Solve an equation f(x) = b 
        /// </summary>
        /// <param name="f"> delegate on the function f</param>
        /// <param name="b"> the value of the function to solve</param>
        /// <param name="i1"> the low part of the segment </param>
        /// <param name="i2"> the high part of the segment </param>
        /// <param name="oType"> the type of method to use </param>
        /// <returns> i1 where b included in [f(i1),f(i2)] and i2 = i1 + 1</returns>
        public static BigInt SolveUnaryFunction(UnaryFunction f, BigInt b, BigInt i1, BigInt i2, SolveType oType)
        {
            switch (oType)
            {
                case SolveType.Dichotomy:
                    return SolveDichotomy(f, b, i1, i2);

                default:
                    // As oType is an enum type, we should never pass through this codeline
                    throw new ArithmeticException("No such method to solve equations");

            }
        }

        /// <summary>
        /// Evaluates the PPCM of bi1 and bi2. Both numbers are positive
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> PPCM of bi1 and bi2 </returns>
        public static BigInt PPCM(BigInt bi1, BigInt bi2)
        {
            if (bi1.m_iSign <= 0 || bi2.m_iSign <= 0)
                throw new ArithmeticException("Can't calculate PGCD of 2 negative numbers");

            BigInt[] a1 = PrimeFactorsPower(bi1);
            BigInt[] a2 = PrimeFactorsPower(bi2);
            BigInt biRes = BigInt.One;
            int iCpt1 = 0;
            ArrayList alRes = new ArrayList();

            // Copy a1 in alRes
            for (iCpt1 = 0; iCpt1 < a1.Length; iCpt1 += 2)
            {
                alRes.Add((BigInt)a1[iCpt1]);
                alRes.Add((int)a1[iCpt1 + 1]);
            }

            iCpt1 = 0;
            // Browse alRes & modify the power values
            for (int iCpt2 = 0; iCpt2 < a2.Length; iCpt2 += 2)
            {
                if (iCpt1 <= a1.GetUpperBound(0))
                    switch (BigInt.Compare(a1[iCpt1], a2[iCpt2]))
                    {
                        case BigInt.CompareType.Equal:
                            alRes[iCpt1 + 1] = Math.Min((int)alRes[iCpt1 + 1], (int)a2[iCpt2]);
                            iCpt1 += 2;
                            break;

                        case BigInt.CompareType.Greater:
                            alRes.Insert(iCpt1, (int)a2[iCpt2 + 1]);
                            alRes.Insert(iCpt1, (BigInt)a2[iCpt2]);
                            break;

                        case BigInt.CompareType.Lesser:
                            while (iCpt1 <= a1.GetUpperBound(0) && a1[iCpt1] < a2[iCpt2])
                                iCpt1 += 2;
                            break;
                    }
                else
                {
                    alRes.Add(a2[iCpt2]);
                    alRes.Add(a2[iCpt2 + 1]);
                }
            }

            // Generate the final number by browsing the ArrayList
            for (int i = 0; i < alRes.Count; i += 2)
            {
                biRes *= Pow((BigInt)alRes[i], (int)alRes[i + 1]);
            }

            return biRes;
        }

        /// <summary>
        /// Evaluates the PGCD of bi1 and bi2. Both numbers are positive
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> PGCD </returns>
        public static BigInt PGCD(BigInt bi1, BigInt bi2)
        {
            if (bi1.m_iSign <= 0 || bi2.m_iSign <= 0)
                throw new ArithmeticException("Can't calculate PGCD of 2 negative numbers");

            BigInt[] a1 = PrimeFactorsPower(bi1);
            BigInt[] a2 = PrimeFactorsPower(bi2);
            int iCpt1 = 0;
            int iCpt2 = 0;
            BigInt biRes = BigInt.One;
            bool bEnd = false;

            while (!bEnd)
            {
                if (a1[iCpt1] == a2[iCpt2])
                {
                    biRes *= Pow(a1[iCpt1], Math.Min((int)a1[iCpt1 + 1], (int)a2[iCpt2 + 1]));
                    iCpt1 += 2;
                    iCpt2 += 2;
                }

                if (iCpt2 <= a2.GetUpperBound(0))
                    while (iCpt1 <= a1.GetUpperBound(0) && a1[iCpt1] < a2[iCpt2])
                        iCpt1 += 2;

                if (iCpt1 <= a1.GetUpperBound(0))
                    while (iCpt2 <= a2.GetUpperBound(0) && a1[iCpt1] > a2[iCpt2])
                        iCpt2 += 2;

                bEnd = (iCpt1 > a1.GetUpperBound(0) || iCpt2 > a2.GetUpperBound(0));
            }

            return biRes;
        }

        /// <summary>
        /// Get all prime factors
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> the list of the prime factors</returns>
        public static BigInt[] PrimeFactors(BigInt bi)
        {
            if (bi.m_iSign <= 0)
                throw new ArithmeticException("Can't calculate prime factors on negative numbers");

            ArrayList al = new ArrayList();

            if (bi == BigInt.One)
            {
                al.Add(bi);
                return (BigInt[])al.ToArray(typeof(BigInt));
            }

            // Div by 2
            while (Even(bi))
            {
                bi = bi / BigInt.Two;
                al.Add(BigInt.Two);
            }

            // Div by 3
            while (bi.DigitsSum() % BigInt.Three == 0)
            {
                bi = bi / BigInt.Three;
                al.Add(BigInt.Three);
            }

            // Div by 5
            while (bi.m_aNumbers[0] % 5 == 0)
            {
                bi = bi / BigInt.Five;
                al.Add(BigInt.Five);
            }

            BigInt biSqrt = Sqrt(bi) + 1;
            for (BigInt i = 7; i <= biSqrt; i += 2)
            {
                if (i.m_aNumbers[0] % 5 != 0 || i.DigitsSum() % 3 != 0)
                    if (bi % i == BigInt.Zero)
                    {
                        bi = bi / i;
                        al.Add(i);
                    }
            }

            if (bi != BigInt.One) al.Add(bi);

            return (BigInt[])al.ToArray(typeof(BigInt));

        }

        /// <summary>
        /// List of divisors
        /// </summary>
        /// <param name="bi"> BigInt </param>
        /// <returns> the list of divisors of bi</returns>
        public static BigInt[] Divisors(BigInt bi)
        {
            if (bi.m_iSign == 0)
                return new BigInt[1] { BigInt.Zero };

            int iSign = bi.m_iSign;
            bi = Abs(bi);

            ArrayList alRes = new ArrayList();
            alRes.Add(BigInt.One);

            BigInt biTwo = bi / BigInt.Two;

            for (BigInt i = 2; i <= biTwo; i++)
                if (bi % i == 0) alRes.Add(i);

            alRes.Add(bi);

            if (iSign == -1)
            {
                ArrayList alRes2 = new ArrayList();

                foreach (BigInt bi2 in alRes)
                {
                    alRes2.Add(bi2);
                    alRes2.Insert(0, -bi2);
                }
                return (BigInt[])alRes2.ToArray(typeof(BigInt));
            }
            else
                return (BigInt[])alRes.ToArray(typeof(BigInt));
        }

        /// <summary>
        /// Test if bi is a prime number
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> true if bi is prime number, otherwise false (negative numbers not considered as prime numbers)</returns>
        public static bool IsPrime(BigInt bi)
        {
            if (bi.m_iSign <= 0) return false;
            if (bi == BigInt.One) return false;

            if (bi == BigInt.Two || bi == new BigInt(3) || bi == new BigInt(5)) return true;

            // Test easy divisors
            if (Even(bi)) return false;                    // div by 2
            if (bi.m_aNumbers[0] % 5 == 0) return false; // div by 5
            // div by 3
            long iMod3 = 0;
            for (int i = 0; i <= bi.m_iTopArray; i++)
            {
                iMod3 += bi.m_aNumbers[i] % 3;
                iMod3 = iMod3 % 3;
            }
            if (iMod3 == 0) return false;

            BigInt biSqrt = Sqrt(bi) + BigInt.One;

            for (BigInt i = new BigInt(7); i <= biSqrt; i = i + BigInt.Two)
            {
                if (bi % i == BigInt.Zero) return false;
            }

            return true;
        }

        /// <summary>
        /// Sqrt(bi). bi must be positive : otherwise throw exception
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> the integer part of the square root of bi </returns>
        public static BigInt Sqrt(BigInt bi)
        {
            if (bi.m_iSign == 0)
                return BigInt.Zero;

            if (bi.m_iSign < 0)
                throw new ArithmeticException("Can not calculate negative Square root");

            return SolveDichotomy(new UnaryFunction(Square), bi, 0, bi);
        }

        /// <summary>
        /// Pow(bi1,i2). i2 must be positive : otherwise throw exception
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="i2"> int </param>
        /// <returns> bi1 ^ i2 </returns>
        public static BigInt Pow(BigInt bi1, int i2)
        {
            if (i2 < 0)
                throw new ArithmeticException("Can not calculate negative power");

            if (i2 == 0)
                return BigInt.One;

            BigInt biPow = bi1.Clone();
            for (int i = 1; i < i2; i++)
            {
                biPow *= bi1;
            }

            if (i2 % 2 == 0)
                biPow.m_iSign = 1;
            else
                biPow.m_iSign = bi1.m_iSign;

            biPow.Canonize();
            return biPow;
        }

        /// <summary>
        /// Pow10(i). i must be positive : otherwise throw exception
        /// </summary>
        /// <param name="i"></param>
        /// <returns> 10 ^ i </returns>
        public static BigInt Pow10(int i)
        {
            if (i < 0)
                throw new ArithmeticException("Can not calculate negative power");

            if (i == 0)
                return BigInt.One;

            BigInt biRes = BigInt.CreateBigInt(i / BigInt.LENBASENUMBER);
            biRes.m_aNumbers[biRes.m_iTopArray] = (int)Calculus.Pow(10, i % BigInt.LENBASENUMBER);

            return biRes;
        }

        /// <summary>
        /// Even
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> true if bi is even</returns>
        public static bool Even(BigInt bi)
        {
            return (bi.m_aNumbers[0] % 2 == 0);
        }

        /// <summary>
        /// Odd
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> true if bi is odd</returns>
        public static bool Odd(BigInt bi)
        {
            return (bi.m_aNumbers[0] % 2 != 0);
        }

        /// <summary>
        /// Factoriel 
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> BigInt</returns>
        public static BigInt Fact(BigInt bi)
        {
            if (bi < BigInt.Zero)
                throw new ArithmeticException("Can not calculate negative factoriels");

            if (bi > BigInt.Zero)
            {
                BigInt biRes = BigInt.One;
                for (BigInt biLoop = BigInt.One; biLoop <= bi; biLoop++)
                {
                    biRes = biRes * biLoop;
                }

                return biRes;
            }
            else
                return BigInt.One;
        }

        /// <summary>
        /// Return the absolute value of a bigint
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> bigint</returns>
        public static BigInt Abs(BigInt bi)
        {
            if (bi.m_iSign == 0)
                return bi.Clone();
            else
            {
                BigInt bi2 = BigInt.CreateBigInt(bi.m_iTopArray);
                bi2.m_iTopArray = bi.m_iTopArray;
                bi2.m_aNumbers = bi.m_aNumbers;
                bi2.m_iSign = 1;
                bi2.Canonize();
                return bi2;
            }
        }

        /// <summary>
        /// Max(bi1,bi2)
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> BigInt </returns>
        public static BigInt Max(BigInt bi1, BigInt bi2)
        {
            if (bi1 > bi2)
                return bi1;
            else
                return bi2;
        }

        /// <summary>
        /// Min(bi1,bi2)
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> BigInt </returns>
        public static BigInt Min(BigInt bi1, BigInt bi2)
        {
            if (bi1 < bi2)
                return bi1;
            else
                return bi2;
        }
        /// <summary>
        /// Returns the quotient and the modulo of bi1 and bi2
        /// </summary>
        /// <param name="bi1">BigInt</param>
        /// <param name="bi2">BigInt</param>	
        /// <paramref name="biMod"/> bi1 modulo bi2</param>
        /// <returns> the quotient of bi1 and bi2 </returns>
        public static BigInt Division(BigInt bi1, BigInt bi2, ref BigInt biMod)
        {
            if (bi2 == BigInt.Zero)
                throw new ArithmeticException("division by zero");

            if (bi2 == BigInt.One)
                return bi1;

            if (bi1 == BigInt.Zero)
                return BigInt.Zero;

            BigInt bi3 = Divide(Abs(bi1), Abs(bi2), ref biMod);
            if (bi1.m_iSign == bi2.m_iSign)
                bi3.m_iSign = 1;
            else
                bi3.m_iSign = -1;

            biMod.m_iSign = bi1.m_iSign;

            biMod.Canonize();
            bi3.Canonize();
            return bi3;
        }
        #endregion

        #region Private methods
        private static BigInt SolveDichotomy(UnaryFunction f, BigInt bi, BigInt i1, BigInt i2)
        {
            BigInt bi1 = f(i1);
            BigInt bi2 = f(i2);
            BigInt biRes = null;
            BigInt i = null;

            do
            {
                i = (i1 + i2) / BigInt.Two;
                biRes = f(i);
                if (biRes > bi)
                    i2 = i;
                else
                    i1 = i;
            } while (i2 - i1 != 1);

            return i1;
        }


        // Square method : use to calculate Square Root
        private static BigInt Square(BigInt x)
        {
            return x * x;
        }

        private static BigInt[] PrimeFactorsPower(BigInt bi)
        {
            BigInt[] biTab = PrimeFactors(bi);
            ArrayList alRes = new ArrayList();

            if ((biTab.GetUpperBound(0)) == 0)
            {
                alRes.Add(biTab[0]);
                alRes.Add(BigInt.One);
                return (BigInt[])alRes.ToArray(typeof(BigInt));
            }

            int iPow = 1;
            BigInt i = null;
            BigInt i1 = null;
            int iMax = biTab.GetUpperBound(0);

            for (int iCpt = 0; iCpt < iMax; iCpt++)
            {
                i = biTab[iCpt];
                i1 = biTab[iCpt + 1];
                if (i == i1)
                    iPow++;
                else
                {
                    alRes.Add(i);
                    alRes.Add((BigInt)iPow);
                    iPow = 1;
                }
            }

            // Add last one
            if (biTab[iMax] != i) iPow = 1;
            alRes.Add(biTab[iMax]);
            alRes.Add((BigInt)iPow);

            return (BigInt[])alRes.ToArray(typeof(BigInt));
        }

        // Return the quotient of bi1 by bi2 and set the modulo
        // bi1 & bi2 positive, bi1 > bi2
        internal static BigInt Divide(BigInt bi1, BigInt bi2, ref BigInt biMod)
        {
            BigInt biQuot = BigInt.CreateBigInt(bi1.m_iTopArray);
            BigInt biNumer = null;
            BigInt biMod2 = BigInt.Zero;

            for (int i = bi1.m_iTopArray; i >= 0; i--)
            {
                biNumer = BigInt.Shift(biMod2, 1) + new BigInt(bi1.m_aNumbers[i]);
                int iQuot = BigInt.DivideBy(biNumer, bi2);
                biQuot.m_aNumbers[i] = iQuot;
                biMod2 = biNumer - BigInt.MultiplyBySmallInt(bi2, iQuot);
            }

            biMod2.Canonize();
            biQuot.Canonize();
            biMod = biMod2;

            return biQuot;
        }
        #endregion
    }
}
